[% setvar title type inference %]
<div id="archive-notice">
    <h3>This file is part of the Perl 6 Archive</h3>
    <p>To see what is currently happening visit <a href="http://www.perl6.org/">http://www.perl6.org/</a></p>
</div>
<div class='pod'>
<a name='TITLE'></a><h1>TITLE</h1>
<p>type inference</p>
<a name='VERSION'></a><h1>VERSION</h1>
<pre>  Maintainer: Steve Fink &lt;<a href='mailto:steve@fink.com'>steve@fink.com</a>&gt;
  Date: 1 Aug 2000
  Last Modified: 27 Aug 2000
  Mailing List: <a href='mailto:perl6-language@perl.org'>perl6-language@perl.org</a>
  Number: 4
  Version: 2
  Status: Developing</pre>
<a name='ABSTRACT'></a><h1>ABSTRACT</h1>
<p>Types should be inferred whenever possible</p>
<a name='CHANGES'></a><h1>CHANGES</h1>
<p>Removed static type declarations. That should be another RFC.</p>
<a name='DESCRIPTION'></a><h1>DESCRIPTION</h1>
<p>For large systems, and often for small ones, type checking is
extremely valuable for optimization and error detection. It is
particularly useful when trying to make global changes without
introducing major errors by forgetting to update code. I propose that
we create a type hierarchy, such as</p>
<pre>   any
      list
         list(T)
      hash
         hash(T1 -&gt; T2)
      scalar
         reference
             object of class T
             ref(T)
         nonref
             number
                integer
      void</pre>
<p>(This is just a sketch; there are many ways of skinning this cat.)
Types will be inferred based on constants and operators. The inference
process would assign a type or set of possible types to every node in
the parse tree. Variables would not have a single type (unless
explicitly constrained by a declaration); they would have a possibly
different type after every assignment. So using the default rules</p>
<pre>   1 $x = 3;
   2 $x .= &quot;x&quot;;
   3 $h{$x} = \$x;
   4 $h{foo} = &quot;bar&quot;;
   5 $x = f();</pre>
<p><i>$x</i> would have type <code>number</code> after line 1 and <code>nonref</code> after line
2. <i>%h</i> would have type <code>hash(nonref -&gt; ref(nonref))</code> after line
3. The effects of line 4 depend on the implementation. Possible
results include <code>hash(nonref -&gt; scalar)</code> and the union type <code>hash(nonref -&gt; ref(nonref)) union hash(nonref -&gt; nonref)</code>. Line 5's
effect depends on whether <code>f()</code>'s type is known. If not, then <i>$x</i>
will have type <code>any</code> after line 5.</p>
<p>Note that so far, all existing programs will always typecheck
successfully, so no burden has been placed on the programmer who does
not want types. Also note that the linear, 1-pass process above is a
dramatic oversimplification of a realistic type inference algorithm.</p>
<a name='MIGRATION'></a><h1>MIGRATION</h1>
<p>None required. The output of p52p6 may be run through the inferencer,
but not even native Perl6 code will be required to make it through the
type inferencer without errors.</p>
<a name='IMPLEMENTATION'></a><h1>IMPLEMENTATION</h1>
<p>Still being thought out. I'm hoping to use Ole Agesen's CPA (Cartesian
Product Algorithm) to deal with functional polymorphism, and some
variant of Plevyak and Chien's iterative algorithm to deal with the
harder problem of data polymorphism.</p>
<a name='ISSUES'></a><h2>ISSUES</h2>
<p>There are several problematic constructs for type inferencing.</p>
<ul>
<li><a name='eval&quot;&quot;'></a>eval&quot;&quot;</li>
<p>Eval&quot;&quot; by default forces the type inferencer to assume the worst for
all subroutine, all global variables, and all lexical variables
captured by a closure. Only very local inference will remain. This
could be controlled by new pragmas, for example a non-overridable
attribute for subroutines (so that its slot in the symbol table will
remain constant), or a pragma to assume that eval&quot;&quot; is read-only with
respect to the symbol table and all variables.</p>
<li><a name='symbolic dereferencing'></a>symbolic dereferencing</li>
<p><code>$x-&gt;f()</code> is a tricky case because $x may be either a reference
or a package name, and determining which <code>f()</code> is being called
requires value inference on <code>$x</code>. A pragma disallowing non-constant
symbolic dereferencing with the arrow operator would help
(<code>Package-&gt;f()</code> is not problematic).</p>
<li><a name='AUTOLOAD'></a>AUTOLOAD</li>
<p>Really just an example of the problems of symbol table manipulation
with respect to type inference. AUTOLOAD means that any function whose
name is not known at compile time (or <i>may</i> not be known, as in
<code>$x-&gt;$f()</code>), must conservatively be assumed to be autoloaded and
execute an eval&quot;&quot; that discards almost all type information.</p>
<li><a name='modularity (caching type information)'></a>modularity (caching type information)</li>
<p>The efficiency of powerful type inferencing algorithms isn't all that
good, and my intuition says that Perl6 is going to need all the power
it can get. Much efficiency can be gained by, for example, maintaining
type information for a module along with its bytecode. (This type
information is more than just the outcome of type inference. It needs
to include templates describing how types propagate through each
subroutine of the module, since modules will generally allow much more
polymorphism than will actually be used in a particular program.)</p>
</ul>
<a name='REFERENCES'></a><h1>REFERENCES</h1>
<p>Ole Agesen. Concrete Type Inference : Delivering Object-Oriented
Applications. PhD thesis, Department of Computer Science of Stanford
University, Published by Sun Microsystem Laboratories (SMLI TR-96-52),
1996.</p>
<p>It's a long thesis, but it's by far the most clear description of type
inferencing that I've found. He uses almost no formulas, and instead
describes things in terms of graphs and pictures. He has a much
shorter paper that summarizes his contributions that I haven't read
yet.</p>
<p>John Plevyak, Andrew A. Chien. Iterative Flow Analysis.
<a href='http://citeseer.nj.nec.com/plevyak95iterative.html' target='_blank'>citeseer.nj.nec.com</a></p>
<p>They wrote a bunch of similar papers, I'm not sure which is best.
Their stuff is tackling data polymorphism more directly, and I think
that's the harder and more important problem for inferring types in
Perl6.</p>
<a name='CONTRIBUTORS'></a><h2>CONTRIBUTORS</h2>
<p>Ken Fox gave some helpful advice and suggestions, particularly to
avoid confusing static type checking with type inference.</p>
<p>Hildo Biersma had several useful comments that I've partly integrated
and am partly still thinking about.</p>
</div>
